package special;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FoolishMistake {
    public static void main(String[] args) {
//        System.out.println(getAll(1000023400));
//        System.out.println(getAll2(1000023400));
//        System.out.println(isZhi(Integer.MAX_VALUE));
        System.out.println(getAll(Integer.MAX_VALUE));

//        long s1 = System.currentTimeMillis();
//        for (int i = 1; i < 1000000; i++) {
//            getAll(i);
//        }
//        long e1 = System.currentTimeMillis();
//        System.out.println("other: " + (e1 - s1));
//
//        long s2 = System.currentTimeMillis();
//        for (int i = 1; i < 1000000; i++) {
//            getAll2(i);
//        }
//        long e2 = System.currentTimeMillis();
//        System.out.println("me: " + (e2 - s2));
    }

    private static List<List<Integer>> getAll(int N) {
        long n = N;
        long i = 2, tmp = (int) n;
        Map<Integer, Integer> map = new HashMap<>();
        while (i * i <= n) {
            if (n % i == 0 && isZhi(i)) {
                while (tmp % i == 0) {
                    tmp /= i;
                    map.put((int) i, map.getOrDefault(i, 0) + 1);
                }
            }
            if (tmp < i)
                break;
            i++;
        }
        if (tmp > 1) {
            map.put((int) tmp, map.getOrDefault(tmp, 0) + 1);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (Integer key : map.keySet()) {
            List<Integer> list = new ArrayList<>();
            list.add(key);
            list.add(map.get(key));
            ans.add(list);
        }
        return ans;
    }

    private static List<List<Integer>> getAll2(int n){
        Map<Integer, Integer> map = new HashMap<>();
        dfs(map, n);
        List<List<Integer>> ans = new ArrayList<>();
        for (Integer key : map.keySet()) {
            List<Integer> list = new ArrayList<>();
            list.add(key);
            list.add(map.get(key));
            ans.add(list);
        }
        return ans;
    }

    private static void dfs(Map<Integer, Integer> map, int n){
        if (isZhi(n)){
            map.put(n, map.getOrDefault(n, 0) + 1);
            return;
        }
        int i = 2;
        while (i * i <= n){
            if (n % i == 0 && isZhi(i)){
                map.put(i, map.getOrDefault(i, 0) + 1);
                dfs(map, n / i);
                return;
            }
            i++;
        }
    }

    private static boolean isZhi(long n) {
        long i = 2;
        while (i * i <= n) {
            if (n % i == 0) {
                System.out.println(i);
                return false;
            }
            i++;
        }
        return true;
    }
}
